Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 71/115

Q: B-tree of order n is a order-n multiway tree in which each non-root node contains __________
A. at most (n – 1)/2 keys
B. exact (n – 1)/2 keys
C. at least 2n keys
D. at least (n – 1)/2 keys
Solution: A non-root node in a B-tree of order n contains at least (n – 1)/2 keys. And contains a maximum of (n – 1) keys and n sons.
Q: Which of the following is the most widely used external memory data structure?
A. AVL tree
B. B-tree
C. Red-black tree
D. Both AVL tree and Red-black tree
Solution:  In external memory, the data is transferred in form of blocks. These blocks have data valued and pointers. And B-tree can hold both the data values and pointers. So B-tree is used as an external memory data structure.
Q: A B-tree of order 4 and of height 3 will have a maximum of _______ keys.
A. 255
B. 63
C. 127
D. 188
Solution: A B-tree of order m of height h will have the maximum number of keys when all nodes are completely filled. So, the B-tree will have n = (mh+1 – 1) keys in this situation. So, required number of maximum keys = 43+1 – 1 = 256 – 1 = 255.
Q: Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
A. 14
B. 7
C. 11
D. 5
Solution: If s splits occur in a B-tree, 2s + 1 nodes are written (2 halves of each split and the parent of the last node split). So, if 5 splits occurred, then 2 * 5 + 1, i.e. 11 nodes are written.
Q: B-tree and AVL tree have the same worst case time complexity for insertion and deletion.
A. True
B. False
C. ...
D. ...
Solution: Both the B-tree and the AVL tree have O(log n) as worst case time complexity for insertion and deletion.
Q: 2-3-4 trees are B-trees of order 4. They are an isometric of _____ trees.
A. AVL
B. AA
C. 2-3
D. Red-Black
Solution: 2-3-4 trees are isometric of Red-Black trees. It means that, for every 2-3-4 tree, there exists a Red-Black tree with data elements in the same order.
Q: What is the best case height of a B-tree of order n and which has k keys?
A. logn (k+1) – 1
B. nk
C. logk (n+1) – 1
D. klogn
Solution: B-tree of order n and with height k has best case height h, where h = logn (k+1) – 1. The best case occurs when all the nodes are completely filled with keys.
Q: Compression techniques can be used on the keys to reduce both space and time requirements in a B-tree.
A. True
B. False
C. ...
D. ...
Solution: The front compression and the rear compression are techniques used to reduce space and time requirements in B-tree. The compression enables to retain more keys in a node so that the number of nodes needed can be reduced.
Q: Which of the following is true?
A. larger the order of B-tree, less frequently the split occurs
B.  larger the order of B-tree, more frequently the split occurs
C. smaller the order of B-tree, more frequently the split occurs
D. smaller the order of B-tree, less frequently the split occurs
Solution: The average probability of the split is 1/(⌈m / 2⌉ – 1), where m is the order of B-tree. So, if m larger, the probability of split will be less.
Q:  In a B+ tree, both the internal nodes and the leaves have keys.
A. True
B. False
C. ...
D. none
Solution: In a B+ -tree, only the leaves have keys, and these keys are replicated in non-leaf nodes for defining the path for locating individual records.

You Have Score    /10